//#include<iostream>
//#include<vector>
//using namespace std;
///////////动态规划
//int maxSubArray(vector<int>& nums) {
//    int len = nums.size();
//    vector<int> dp(len);
//    dp[0] = nums[0];
//    int ans = dp[0];
//    for (int i = 1; i < len; i++)
//    {
//        dp[i] = max(dp[i - 1] + nums[i], nums[i]); //选择接上以前的，或重新开始
//        ans = max(ans, dp[i]);//更新子数组最大值
//    }
//    return ans;
//}
//int main()
//{
//    vector<int> nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
//    cout << maxSubArray(nums) << endl;
//    //输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
//    //输出：6
//    //解释：连续子数组[4, -1, 2, 1] 的和最大，为 6 。
//}